#include<iostream>
#include<set>
#include<string>
using namespace std;
/*
set 和multiset通常用平衡二叉树(balanced binary tree, 确切说是红黑树)实现。
这样在插入数据时能自动排序, 使得查找元素时有良好性能。
其查找函数具有对数O(logn)时间复杂度。
但是,自动排序也造成set和multiset的一个重要限制:你不能直接改变元素值，
因为这样会打乱原本正确的顺序。
从其接口也能反映这种情况:
set和multiset不提供任何函数可以直接访问元素。
通过迭代器访问元素时都是常量。
双向迭代器
不支持下标访问 p[]
增删查，不支持修改
*/
//集合
//set特定：
//1. 容器不允许有重复 
//2.所有的元素在插入的时候自定被排序


//set 容器构造和赋值
//void printSet(const set<int>& s)
//{
//	for (auto i : s)
//		cout << i << " ";
//	cout << endl;
//}
//void test()
//{
//	set<int>s{ 1,2,3 };
//	//插入数据，只有insert方式
//	s.insert(4);
//	s.insert(5);
//	printSet(s);
//
//	//拷贝构造
//	set<int>s1;
//	s1 = s;
//	printSet(s1);
//
//}
//int main()
//{
//	test();
//	return 0;
//}



//set大小和交换
//size（）
//empty（）
//

//void printSet(const set<int>& s)
//{
//	for (auto i : s)
//		cout << i << " ";
//	cout << endl;
//}
//void test()
//{
//	set<int>s{ 3,2,1 }; //默认是升序
//	//插入数据，只有insert方式
//	s.insert(4);
//	s.insert(5);
//	printSet(s);
//	
//	set<int>s1;
//	s1 = s;
//
//	//1 2 3 4 5
//	//size() 计算大小
//	cout<<"set的大小是"<<s.size() << endl;
//
//	//empty() 判空
//	cout << s.empty() << endl;
//	
//	s.swap(s1);
//	printSet(s1);
//}
//int main()
//{
//	test();
//	return 0;
//}


//set插入和删除
//void printSet(const set<int>& s)
//{
//	for (auto i : s)
//		cout << i << " ";
//	cout << endl;
//}
//void test()
//{
//	set<int>s{ 1,2,3 };
//	//插入数据，只有insert方式
//	s.insert(4);
//	s.insert(5);
//	printSet(s);
//
//	//拷贝构造
//	set<int>s1;
//	s1 = s;
//	printSet(s1);
//
//	//删除
//	s.erase(s.begin());
//	printSet(s); 
//
//	//删除重载版本
//	s.erase(2);
//	printSet(s);
//
//	//清空 也可以用clear
//	s.erase(s.begin(), s.end()); //全删除
//	printSet(s);
//
//
//
//}
//int main()
//{
//	test();
//	return 0;
//}


//查找和统计
//find(key)   返回该值的迭代器，若不存在，则返回尾部迭代器
//count(key)   返回个数
//void printSet(const set<int>& s)
//{
//	for (auto i : s)
//		cout << i << " ";
//	cout << endl;
//}
//void test()
//{
//	set<int>s{ 10,20,30 };
//	//插入数据，只有insert方式
//	s.insert(40);
//	s.insert(50);
//	printSet(s);
//
//	//拷贝构造
//	set<int>s1;
//	s1 = s;
//	printSet(s1);
//
//	//find()
//	auto pos = s.find(30);
//	cout << "返回的位置的值是" << *pos << endl;
//	
//	//统计30的个数
//	int num = s.count(30);
//	//对于set而言，统计的结果要么是0，要么是1
//	cout << num << endl;
//
//
//}
//int main()
//{
//	test();
//	return 0;
//}




///set默认排序的规则是从小到大
//set容器排序

//class myCompare//仿函数
//{
//public:
//	bool operator()(const int v1, const int v2)
//	{
//		return v1 > v2;
//	}
//};
//
//
//void test()
//{
//	set<int>s{ 1,243,2,42,42 };//默认已经升序排序好
//	for (auto it = s.begin();it != s.end();it++)
//		cout << *it << " ";
//	cout << endl;
//
//	//修改数据的排序规则
//	set<int, myCompare>s2;
//	s2.insert(2);
//	s2.insert(21);
//	s2.insert(-1);
//	s2.insert(100);
//
//	for (auto it = s2.begin();it != s2.end();it++)
//		cout << *it << " ";
//	cout << endl;
//
//
//}
//int main()
//{
//	test();
//	return 0;
//}


//
//int main()
//{
//	set<int>s1{ 1,2,2,0,9,3 };
//	for (auto x : s1)
//		cout << x;//自动去重和排序
//
//
//
//	return 0;
//}